package com.chj.chuji.tijie14;

import java.util.ArrayList;
import java.util.List;

//https://www.luogu.com.cn/blog/fsy2017/solution-p2996
//https://blog.csdn.net/u013686535/article/details/70226392
//https://blog.csdn.net/getsum/article/details/51613123
public class Visitcows {

	public static class Employee {
		public int happy; // 这名员工可以带来的快乐值
		public List<Employee> nexts; // 这名员工有哪些直接下级
		public boolean isLai;

		public Employee(int happy, boolean isLai) {
			this.happy = happy;
			this.nexts = new ArrayList<Employee>();
			this.isLai = isLai;
		}
	}

	public static int maxHappy(Employee boss) {
		Info headInfo = process(boss);
		return Math.max(headInfo.laiMaxHappy, headInfo.buMaxHappy);
	}

	public static class Info {
		public int laiMaxHappy;
		public int buMaxHappy;

		public Info(int lai, int bu) {
			laiMaxHappy = lai;
			buMaxHappy = bu;
		}
	}

	public static Info process(Employee x) {
		if (x.isLai) { // x是基层员工的时候
			return new Info(0, 0);
		}

		x.isLai = true;
		int lai = x.happy; // x来的情况下，整棵树最大收益
		int bu = 0; // x不来的情况下，整棵树最大收益
		for (Employee next : x.nexts) {
			Info nextInfo = process(next);
			lai += nextInfo.buMaxHappy;
			bu += Math.max(nextInfo.laiMaxHappy, nextInfo.buMaxHappy);
		}
		return new Info(lai, bu);
	}

	public static void main(String[] args) {
		Employee head = new Employee(1, false);
		Employee c02 = new Employee(1, false);
		Employee c03 = new Employee(1, false);
		Employee c04 = new Employee(1, false);
		Employee c05 = new Employee(1, false);
		Employee c06 = new Employee(1, false);
		Employee c07 = new Employee(1, false);

		head.nexts.add(c02);
		c02.nexts.add(c06);
		c02.nexts.add(c03);
		c06.nexts.add(c05);
		c06.nexts.add(c07);
		c03.nexts.add(c04);
		c05.nexts.add(c06);
		c07.nexts.add(c06);
		c04.nexts.add(c03);

		System.out.println(maxHappy(head));
	}
}

//#include<iostream>
//#include<cstdio>
//using namespace std;
//int NEXT[100005],END[100005],last[100005];
//int f[100005][2],cnt,n;
//bool mark[100005];//判断该节点是否已经讨论过
//void insert(int a,int b){
//	END[++cnt]=b;
//	NEXT[cnt]=last[a];
//	last[a]=cnt;
//}
//void dp(int x){
//	mark[x]=1;
//	f[x][1]=1,f[x][0]=0;
//	int j,i;
//	for(i=last[x];i;i=NEXT[i]){
//		j=END[i];
//		if(mark[j])continue;
//		dp(j);
//		f[x][1]+=f[j][0];
//		f[x][0]+=max(f[j][1],f[j][0]);
//	}
//}
//int main(){
//	scanf("%d",&n);
//	int i,x,y;
//	for(i=1;i<n;i++){
//		scanf("%d%d",&x,&y);
//		insert(x,y);
//		insert(y,x);
//	}
//	dp(1);//这里用图中任意一个点来作为讨论的起点
//	cout<<max(f[1][1],f[1][0]);
//}
